\documentclass[a4paper,11pt]{article}
\usepackage[pdftex]{graphicx}

\title{}
\date{4 May 2012}
\author{Mark Larsen, Zach O'Connor, and Mark Swatosh\\Department of Computer Science, University of Minnesota}




\begin{document}

\maketitle{}

\tableofcontents{} \newpage




\section{Workload per team member}

% searched for an open source tetris clone
% set up svn repository, through google code
% added support for AI in game controller
% added extra functionality to 
% did math to generate successor boards given a current board and a next tetrominoe
% wrote heuristic, tweaked heuristic... tweaked heuristic... tweaked heuristic... tweaked heuristic... tweaked heuristic...
% wrote stupid AI (worse than random)... GBFS, DLBFS, minimax with depth 1 and 2
% working multithreading - that turned out to not help
% created frankenstein pieces, wrote frankenminimax with depth 1 and 2

\subsection{Mark Larsen}

\begin{itemize}
\item searched for an open source tetris clone
\item set up svn repository, through google code
\item added support for AI in game controller
\item extended functionality of tetris client (described in tools section)
\item wrote stupid AI (worse than random)... GBFS, DLBFS, minimax with depth 1 and 2
\item wrote heuristic, tweaked heuristic... tweaked heuristic... tweaked heuristic... tweaked heuristic... tweaked heuristic...
\item created frankenstein pieces, wrote frankenminimax with depth 1 and 2
\end{itemize}

\subsection{Zach}

\begin{itemize}
\item added support for AI in game controller
\item did math to generate successor boards given a current board and a next tetrominoe
\item wrote heuristic, tweaked heuristic... tweaked heuristic... tweaked heuristic... tweaked heuristic... tweaked heuristic...
\item wrote papers
\end{itemize}

\subsection{Mark Swatosh}

\begin{itemize}
\item working multithreading - that turned out to not help
\item research on multithreading in python - to prove that it is horrible
\item wrote stupid AI (worse than random)... GBFS, DLBFS, minimax with depth 1 and 2
\item created frankenstein pieces, wrote frankenminimax with depth 1 and 2
\item wrote papers
\end{itemize}




\section{Tools used}

We used the tetris\_tk tetris client, which was implemented using the Tkinter graphics package. tetris\_tk is open source, found on Google Code. The author is simon.pe...@gmail.com, who omitted part of his email to prevent spam.

After taking his code, we modified and extended it in the following manner

\begin{itemize}
\item display next piece in upper right hand corner (it didn't do this before)
\item border around the actual play grid (so that it is clear where the walls and the bottom of the playable area is)
\item speed controls - up and down keys increase and decrease the speed of the AI
\item implemented batch running - tetris will restart as soon as it loses, up to that number of executions
\item command line input - parameters to select which AI player, and how many batches to run
\item data tracking - window displays current, average, and highest number of rows cleared,and the number runs of the algorithm
\end{itemize}





\section{Effort}

% searched for an open source tetris clone
% set up svn repository, through google code
% added support for AI in game controller
% added extra functionality to display next piece and border, speed controls, 
%     command line parameter interpreting, implemented batch running, data tracking (average and best case results)
% did math to generate successor boards given a current board and a next tetrominoe
% wrote heuristic, tweaked heuristic... tweaked heuristic... tweaked heuristic... tweaked heuristic... tweaked heuristic...
% wrote stupid AI (worse than random)... GBFS, DLBFS, minimax with depth 1 and 2
% multithreaded - except that multithreading was horrible...
% created frankenstein pieces, wrote frankenminimax with depth 1 and 2

\subsection{A non-obvious solution}
When we started to work, one of our members suggested that Minimax would be a good algorithm for playing Tetris. However, the others, as well as almost everyone we talked to, was unconvinced that Minimax would be able to play Tetris well, since tetris is a non-adversarial game, where each tetrominoe is selected randomly. We agreed to implement it simply to try it out. We were all very surprised to see that Minimax, especially Minimax2, can actually clobber any other AI we made, when time wasn't a factor. Granted, it can't play Tetris in real time situations, but what we learned was very interesting - that Minimax can be applied in non-adversarial situations, particularly in environments where some choice is made outside of the AI's control.

\subsection{Value of the results}
Minimax can be applied to more than strictly adversarial problems

\subsection{Difficulty}

\begin{itemize}

\item Challenges $\backslash$ Limitations with Python. We got multithreading working perfectly well, which caused python to use up twice as many resources and run just as fast as it had before.

\item Lots of math involved with generating children boards. So many off by 1 errors...

\item Lots of testing and debugging when the math wasn't working correctly.

\item Making an illegal intermediate move on the way to a legal final position caused the block to be placed somewhere the AI didn't want it, which interfered with evaluating the AI algorithm performance.

\item Uhh... This.

\end{itemize}

\includegraphics[width=3in]{DLBFS_line_fail}

This was our DLBFS algorithm, the one that had already cleared 1348 lines. We discovered that, if it was given two identical pieces that it would place in two separate locations, it could place them in either order and get the same result after two moves. The algorithm would always place the one with fewer rotations and further left before the other, even if the latter move was actually the better of the two. And after that it would recalculate and discover the same situation. Essentially, it infinitely deferred clearing lines.

\subsection{Generating Results}
Click run and sit for 8 hours, waiting for the processor-intensive algorithms to finish generating results for 100 games. And that was the second fastest AI algorithm we made...




\end{document}








